3-26 14. 最长公共前缀

Date：2022-03-26 10:20:28

标签：

• 横向扫描

题目：14. 最长公共前缀 ( 简单😄 )

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 ""。

示例

示例1：

输入：strs = ["flower","flow","flight"]
输出："fl"

示例2：

输入：strs = ["dog","racecar","car"]
输出：""
解释：输入不存在公共前缀。

分析

• 横向扫描

• 纵向扫描

题解

横向扫描

function longestCommonPrefix(strs: string[]): string {
  const len = strs.length

  if (len <= 0) {
    return ''
  }

  let answer = strs[0]
  for (let i = 1; i < len; ++i) {
    const curr = strs[i]

    answer = longest(answer, curr)
  }

  return answer

  function longest(pre: string, curr: string): string {
    let i = 0
    while (pre[i] && curr[i]) {
      if (pre[i] != curr[i]) {
        break
      }
      ++i
    }

    return pre.slice(0, i)
  }
}

纵向扫描

function longestCommonPrefix111(strs: string[]): string {
  const len = strs.length
  if (len <= 0) {
    return ''
  }

  let maxLen = -Infinity
  for (let i = 0; i < len; ++i) {
    maxLen = Math.max(maxLen, strs[i].length)
  }

  for (let i = 0; i < maxLen; ++i) {
    let mark = strs[0][i]
    for (let j = 1; j < len; ++j) {
      if (strs[j][i] != mark) {
        return strs[0].slice(0, i)
      }
    }
  }

  return strs[0]
}

使用

function main() {
  const strs = ['flower', 'flow', 'flight']
  // const strs = ['dog', 'racecar', 'car']
  // const strs = ['a']

  console.log('[]:', longestCommonPrefix(strs))
  console.log('[]:', longestCommonPrefix111(strs))
}

main()

export {}